A connected graph is any means of displaying a number of nodes (typically represented by points), and links (typically represented by lines between such points) connecting such nodes. Such connected graphs are used in mathematics to represent theoretical or real scenarios involving multiple nodes and the interconnections between them. In commercial applications, such graphs are used in industries such as the transportation industry to show transportation connections between cities, or subway stations for example, or in the telecommunications industry to display communication links between communication nodes.
In typical connected graphs, the nodes are positioned geographically or logically, such that the position of such nodes provides some information to the viewer of the connected graph. An example of such a connected graph for either a transportation or telecommunication network is shown in FIG. 1. In this example, the nodes are displayed in a pseudo-geographical organization to communicate the relative location of each set of nodes. This method of displaying nodes and links is suitable where the number of nodes is relatively low, and the interconnections between the nodes are simple, such that there are only a few links connecting the nodes. However, where there are either a large number of nodes, a large number of interconnections between the nodes, or some combination thereof, such a connected graph can become extremely complex such that it becomes impossible for the viewer to extract any useful information from it. An example of such a complex connected graph is shown in FIG. 2. The representation of the links connecting the nodes become so dense that it forms a tight mesh, making it very difficult for the viewer to tell which links connect which nodes. This problem is very common in telecommunication applications where there can be dozens or even hundreds of highly interconnected nodes in a given network.
Several efforts have been made at solving the problem of complex connected graphs. Basic solutions include using different colours and/or line thicknesses for different links. In other efforts, the geographical or logical placement of the nodes is abandoned in favour of reducing the complexity of the connected graph. In such examples, the nodes may be arranged in a circle with links between the nodes forming arcs across the circle, Alternatively, the nodes and links may be represented in a three-dimensional fashion other solutions include methods of viewing portions of complex connected graphs with greater clarity. For example, a “visual fish eye” or virtual magnifying glass may be used to expand a portion of the graph for easier viewing. However, these efforts provide only partial solutions since again, as the number of nodes and the interconnections between them increases, the graphs become, increasingly complex such that extracting any information from them becomes extremely difficult.
A further problem adding to the complexity of such graphs is introduced by telecommunication applications in which there are often several communication links between any two nodes. For example, a single fiber-optic bundle connecting two nodes may contain hundreds of individual cables, each of which must be represented on the connected graph.
Additionally, it is often desirable in real-world applications of connected graphs to visually provide some information about the links. For example, it may be desirable to communicate the status of a communication link, or the frequency of flights for an air link. Such information may be provided by using different colours, or different link representations (dashed lines, for example). However, such information is lost when the connected graph becomes complex.